package com.ry.day1129;

public class LC1037 {

    static class Solution {
        /**
         * @param a: an array
         * @return: is the number of global inversions is equal to the number of local inversions
         */
        public boolean isIdealPermutation(int[] a) {
            int n= a.length;
            int jubunixu = 0; //局部逆序数的个数
            for (int i = 0; i < n-1; i++) {
                if(a[i]>a[i+1]) jubunixu++;
            }
            int quanjunixu = 0;  //全局逆序数的个数

            //归并排序求全局逆序数的个数
            int step =1; //1  2  4  8   步长
            while (step<n) {
                int left = 0; //左组开始的位置
                while (left<n) {
                    int m = left+step-1; //左组结束的位置
                    if(m>n-1) break;
                    int r = Math.min(m+step,n-1);//右组结束的位置
                    quanjunixu+= guibing(a,left,m,r);
                    left=r+1;
                }
                if(step>n/2) break;
                step=step*2;
            }

            return quanjunixu == jubunixu;
        }

        public int guibing(int[] arr, int l,int m,int r){
            int ans =0;
            int i=0,p1=l,p2=m+1;
            int[] help= new int[r-l+1];
            while (p1<=m&& p2<=r){
                if(arr[p1]<=arr[p2]){
                    help[i++] =arr[p1++];
                }else{
                    ans+=m-p1+1;
                    help[i++] = arr[p2++];
                }
            }

            while (p1<=m){
                help[i++] = arr[p1++];
            }

            while (p2<=r){
                help[i++] = arr[p2++];
            }

            for (int j = 0; j <i ; j++) {
                arr[l+j] = help[j];
            }

            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.isIdealPermutation(new int[]{0,1,2})); //true
        System.out.println(obj.isIdealPermutation(new int[]{1,2,0})); //false
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1037 · 全局和局部逆序数
算法
中等
通过率
72%

题目
题解11
笔记
讨论20
排名
记录
描述
给定一个[0, 1, ...N - 1]的排列A，其中N是A的长度.

全局逆序数是指满足0 <= i < j < N 且 A[i] > A[j]的数量.

局部逆序数是指满足0 <= i < N 且 A[i] > A[i+1]的数量.

如果全局逆序数和局部逆序数相等，返回true，否则返回false.

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


A 是[0, 1, ..., A.length - 1]的一个排列.
A 的长度范围为 [1, 5000].
该题目时间限制比较严格.
样例
样例 1:

输入: [0, 1, 2]
输出: true
解释: 没有全局逆序, 没有局部逆序.
样例 2:

输入: [1, 2, 0]
输出: false
解释: 有两个全局逆序, 一个局部逆序.
标签
企业
Amazon
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
13/46
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
